// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

// countingSort 实现计数排序算法，该算法按升序对整数数组进行排序
func countingSort(array []int) []int {

	// 创建一个计数数组，其大小等于输入数组中的最大元素
	count := makeRange(0, findMax(array))

	// 遍历输入数组，增加遇到的每个元素的计数
	for _, e := range array {
		count[e] += 1
	}

	// 修改计数数组以包含直到每个索引的元素的累积计数
	for i := 1; i < len(count); i++ {
		count[i] += count[i-1]
	}

	// 创建一个与输入数组大小相同的输出数组
	res := make([]int, len(array))

	// 再次遍历输入数组，将每个元素放在输出数组中的正确位置
	for i := 0; i < len(array); i++ {
		e := array[i]
		t := count[e] - 1

		res[t] = e
		count[e] = count[e] - 1
	}

	// 返回排序后的输出数组
	return res
}

// findMax 返回整数输入数组中的最大元素
func findMax(array []int) int {
	var temp int

	temp = array[0]

	for _, e := range array {
		if temp < e {
			temp = e
		}
	}

	return temp
}

// makeRange 返回一个大小为 max-min+1 的整数切片，所有值都初始化为 0
func makeRange(min, max int) []int {
	a := make([]int, max-min+1)
	for i := range a {
		a[i] = 0
	}
	return a
}

func main() {
	array := []int{33, 23, 56, 7, 8, 18, 99, 28}
	res := countingSort(array)
	fmt.Println(res)
}

//$ go run countingSort.go
//[7 8 18 23 28 33 56 99]
